// 笔试强训2025/3/13
// 单词搜索

class Solution {
    public:
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * 
         * @param board string字符串vector 
         * @param word string字符串 
         * @return bool布尔型
         */
        bool find(vector<string>& board, string& word, int pos, int i, int j)
        {
            if(pos == word.size())
                return true;
    
            int tmp = board[i][j];
            board[i][j] = 0;
            int m = board.size(), n = board[0].size();
            if(i > 0 && board[i - 1][j] == word[pos] && find(board, word, pos + 1, i - 1, j))
            {
                return true;
            }
            if(i < m - 1 && board[i + 1][j] == word[pos] && find(board, word, pos + 1, i + 1, j))
            {
                return true;
            }
            if(j > 0 && board[i][j - 1] == word[pos] && find(board, word, pos + 1, i, j - 1))
            {
                return true;
            }
            if(j < n - 1 && board[i][j + 1] == word[pos] && find(board, word, pos + 1, i, j + 1))
            {
                return true;
            }
            board[i][j] = tmp;
            return false;
        }
        
        bool exist(vector<string>& board, string word) {
            // write code here
            int m = board.size(), n = board[0].size();
            for(int i = 0; i < m; i++)
            {
                for(int j = 0; j < n; j++)
                {
                    if(board[i][j] == word[0] && find(board, word, 1, i, j))
                        return true;
                }
            }
            return false;
        }
    };